COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00015 00003	Note of July 4, 1980
C00019 00004	This file is patter.ai[f75,jmc]
C00020 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.cb WHAT IS A PATTERN?


	In many areas of programming and especially in artificial
intelligence, it is effective to create and use patterns.  This
involves recognizing the pattern in a situation and taking
an appropriate action.  More generally, the action taken may depend
on a set of patterns and other information as well.

	The most well developed forms of pattern and pattern
recognition occur in formal syntax of languages where the
languages are strings of symbols.  I want to define patterns
abstractly quite separately from language but hopefully in a way
that is applicable to language and in a way that will enable
some of the properties of linguistic patterns that have been
studied to carry over to ⊗abstract ⊗patterns.

	When I have tried to give a fully general definition of
pattern, the ideas have gotten quite complex and no ⊗most ⊗general 
idea has come out.  Therefore, I will try to sneak up on it
and start with the simplest kinds of patterns.


Type I patterns

	A type I pattern is specified by giving a collection
of predicates and a quantifier free expression in these
predicate symbols.  An instance of the pattern is a pairing of
entities with the free individual variables such that when
the variables are assigned the corresponding entities, the
expression is true.

	The notion of pin in chess can be given as
an example of a type I pattern provided it is described in
terms of the following predicates:

	1. ⊗iswhite(piece) asserts that ⊗piece is white.

	2. ⊗sees(piece1,piece2,direction,board) asserts that
if one moves from ⊗piece1 in the direction ⊗direction 
on the board situation ⊗board, one encounters ⊗piece 
before encountering a non-blank square or the edge of the
board.

	2. ⊗moves(piece,direction) asserts that ⊗piece 
moves an arbitrary distance, (it therefore must be a
queen, rook, or bishop) in ⊗direction. 

	3. ⊗better(piece1,piece2) asserts that ⊗piece1 
has a higher value than ⊗piece2. 

	4. ⊗defended(piece,board) asserts that ⊗piece is
defended in the position ⊗board. 

	Pins are then described by a formula involving five
free variables, namely ⊗piece1 - the pinning piece,
⊗piece2 - the pinned piece, ⊗piece3 - the piece
against which ⊗piece2 is pinned, ⊗direction -
the direction from ⊗piece1 to ⊗piece2, and 
⊗board - the board position in which all this occurs.  The formula
is
	%2iswhite(piece1) ≡ iswhite(piece3) ∧
	iswhite(piece1) ≡ ¬iswhite(piece2) ∧
	sees(piece1,piece2,direction,board) ∧
	sees(piece2,piece3,direction,board) ∧
	moves(piece1,direction) ∧
	[¬defended(piece3,board) ∨ better(piece3,piece1)]%1.
%1

	This simple example suggests the following remarks:

	1. The simplest linguistic patterns are of type I.
These give a special role to the relation

	⊗ispredecessor(string1,string2,string3) 

which asserts that ⊗string1 immediately precedes
⊗string2 in their occurence as substrings of ⊗string3. 

Thus strings consisting of noun phrases followed by verb phrases
which give one form of sentence in some simple grammars are
examples of the pattern

	%2ispredecessor(string1,string2,string3) ∧
	nounphrase(string1) ∧
	verbphrase(string2)%1.

Of course, using this more general notion of pattern gives rise
to something longer than the simple %2S_→_NP_VP%1 given in
the grammars.

	2. Since a substantial part of the generalization we are
looking for consists merely in not giving a special role to the
relation ⊗ispredecessor, it is likely that some of the
interesting properties of string patterns carry over to the
general case.

	3. Given the small number of pieces in a chess position,
it is clearly feasible to find pins in a position given
programs for calculating the predicates involved.  This involves
specifying one of the elements of the pattern, namely ⊗board 
which thereby plays a special role and scanning the others.
An ad hoc pin recognizer is clearly easy to write, and it
is even easy to write a general pattern recognizer for patterns
involving a single board variable, several piece variables, and
several direction variables.
However, a recognizer that had to scan all possible positions
is infeasible and not wanted for chess play anyway.  Moreover,
the different roles played by pieces and directions (e.g. it
if we scan the potential pinning pieces and the directions
leading from them first, we need only look for potential
pinned pieces in the given direction), makes it unlikely that
the techniques of grammatical pattern recognition have much
carryover to the general case.

	4. One is tempted to use existing patterns in
defining new patterns, and in order to do this, we need to
allow binding some variables with existential quantifiers.
Thus we obviously want to define

	pinned(piece,board) ≡ ∃ piece1 piece3 direction.
		pins(piece1,piece,piece3,direction,board),

and the predicate ⊗defended used in the definition of
⊗pins obviously wants to be defined in terms of a pattern.

	In the study of grammatical patterns, the highly recursive
cases are emphasized, because they are necessary for any kind
of generality, because Chomsky fascinated the linguists
with the competence-performance distinction, and because
they are mathematically the most interesting.  Nevertheless,
non-recursive patterns occur in many practical cases and probably usually
admit simpler methods of recognition and use.
Therefore we shall take type I patterns to be non-recursive,
and reserve recursion for a later type.

	5. In one respect, type I patterns go beyond context free
phrase structure grammars in the string case.  Namely, the
same variable can occur in several places in the defining
expression, and this allows the imposition of requirements
of agreement from the beginning.  I doubt that the requirement
that all occurences of variables be of different variables
leads to an interesting class of patterns.  Moreover, it
doesn't give the context free patterns in the grammar case
unless we distinguish the ⊗ispredecessor function,
because a variable has to occur in the ⊗ispredecessor 
relation and also in the other predicates.  This simply
confirms my prejudice against context freeness.

	6. In writing the ⊗pin pattern, it was
an inconvenience not to be able to use the function
⊗color(piece), but we got around it with the
predicate ⊗iswhite at the cost of awkwardness.
It would seem that any pattern that can be written
with functions can also be written using only the
corresponding predicates provided we use existential
quantifiers to get rid of unwanted variables that have to
be introduced.  Thus the relation

	%2y = f(g(h(x)))%1

which might occur in some pattern would have to be
replaced by

%2     F(y,u) ∧ G(u,v) ∧ H(v,x)   %1

where ⊗f and ⊗F are related by

%2     ∀ x y.(y = f(x) ≡ F(y,x)).    %1

Thus we would get a pattern with more variables, and the
extras can be eliminated with existential quantifiers.
Suppose we call the patterns we get allowing function
symbols type I-a.  It is an open question whether we should
do this or whether we should admit the function symbols
directly into type I.

	6. We shall not try to define more types of patterns
in this draft.  However, note the following directions of
generalization:

		a. The computation of the predicate expression
could involve more complicated calculations such as recursion.
Thus a pin is not a type I pattern if we can't use
⊗sees(piece1,piece2,direction,board), but have to build
it from the relation ⊗adjacent(square1,square2,direction). 

		b. Variable numbers of entities may appear in
patterns.

		c. The conditions for one pattern may require
the non-existence of other patterns.

	7. The example of pinning shows that patterns may be
used in much more varied ways than in linguistics whether of
natural or computer languages.  Some typology of the ways
in which patterns are used after being recognized is probably
worthwhile.

Note of July 4, 1980

	insts[pat1,pat2,exp,alist] is the list of joint matches of
⊗pat1 and ⊗pat2 with subexpressions of ⊗exp subject to the list
⊗alist of commitments.  There are yet more exotic symbolic
patterns.

	It is important to identify the important cases of
patterns of functions applied to arguments.  Boyer-Moore

	projections and occlusions

	patterns of self-application

Note of July 25, 1980

	1. a collection of concentric circles

	2. a ring consisting of an arbitrary finite set of units

The latter may be a prototype of a graph pattern that will be
more difficult to treat than hierarchical patterns.

	3. An overload in chess where several pieces are jointly
performing more functions (defending more other pieces) than they
can jointly handle.

Are patterns, problems involving pattern matching, circumscription
and mappings into and out of finite spaces enough for a new approach
to AI programs.  Also approximate concepts, especially axiomatized
through contexts of successive levels of detail.

	The collection of concentric circles might be represented by

	%2islist u ∧ ∀v.[non-null-sublist[v,u] ⊃ iscircle qa v
∧ [qn qd v ∨ inside[qad v, qa v]]]%1.

Of course, three concentric circles would be represented by

	%2iscircle x ∧ iscircle y ∧ iscircle z ∧ inside[y,x] ∧ inside[z,y]%1.

It isn't clear what we gain and lose by going to arbitrary collections
of concentric circles.  (I am using the word concentric loosely to mean
that they form a set ordered by ⊗inside.  If they were actually concentric,
we could get by more easily by mentioning the common center).

	We may attempt a recursive definition of a collection of
concentric circles by

%2isconcent x ≡ iscircle x ∨ ∃y z.[iscircle y ∧ isconcent z ∧ inside[z,y]]%1

or

%2isconcent x ≡ iscircle x ∨ iscircle outer x ∧ isconcent inner x ∧
inside[inner x, outer x]%1

	A ring seems more difficult than the concentric circles, because
it can't be handled recursively in such a simple way.
This file is patter.ai[f75,jmc]